שני סבבי ראיונות שני ראיונות בכל אחד ראיונות טכנים
שאלות מתוך הראיון
נתון מערך של זוגות ומספר אחד בלי זוג. איך תמצא את המספר הנל?
תשובות
הוסף תשובה
|
לצפיה בתשובות
מאי 2019
פתרון ראשון: מעבר לינארי על איברי המערך וXOR ביניהם, האיבר היחיד שהביטים שלא לא יתבטלו עם בן הזוג שלו הוא האיבר הבודד, ולכן בתום הפעולה נישאר עם האיבר הבודד.
פתרון שני: במערך לכל איבר יש בן זוג למעט איבר אחד בלבד -> מכאן שמספר איברי המערך אי-זוגי בהכרח.
לכן ניתן לעשות PIVOT סביב החציון ולבחור בחצי בגודל האי-זוגי ולהמשיך ברקרוסיה עד שנישאר עם מערך בגודל 2 ומערך בגודל 1, האיבר הבודד הוא האיבר שאין לו בן זוג. סיבוכיות הזמן במקרה הזה תיהיה גם כן לינארית בכלל הקפיצות האקספוננציאליות. אך בגלל הקבוע הגדול הפתרון הראשון עדיף.